package com.wk.arth.od;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**某公司研发了一款高性能 AI 处理器。每台物理设备具备 8 颗 AI 处理器，编号分别为 0、1、2 、3、4、5、6、7。编号 0-3 的处理器处于同一个链路中，编号 4- 7 的处理器处于另外一个链路中，不通链路中的处理器不能通信，如下图所示。现给定服
 务器可用的处理器编号数组 array，以及任务申请的处理器数量 num，找出符合下列亲和性
 调度原则的芯片组合。如果不存在符合要求的组合，则返回空列表。
 亲和性调度原则：
 \-如果申请处理器个数为 1，则选择同一链路，剩余可用的处理器数量为 1 个的最佳，其次是
 剩余 3 个的为次佳，然后是剩余 2 个，最后是剩余 4 个。
 \-如果申请处理器个数为 2，则选择同一链路剩余可用的处理器数量 2 个的为最佳，其次是剩
 余 4 个，最后是剩余 3 个。
 \- 如果申请处理器个数为 4，则必须选择同一链路剩余可用的处理器数量为 4 个。
 \- 如果申请处理器个数为 8，则申请节点所有 8 个处理器。
 提示：
 1\. 任务申请的处理器数量只能是 1、2、4、8
 2\. 编号 0-3 的处理器处于一个链路，编号 4-7 的处理器处于另外一个链路。
 3\. 处理器编号唯一，且不存在相同编号处理器
 输出为组合列表，当 array=[0, 1, 4, 5, 6, 7] ，num=1 时，输出为[[0], [1]]
 * @author wukai
 * @date 2023/4/22 16:27
 */
public class Chu_li_qi {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer[] arr = Arrays.stream(sc.nextLine().split("[\\[\\]\\,\\s]")).filter(item->!"".equals(item))
                .map(item->Integer.parseInt(item)).toArray(Integer[]::new);
        String num = sc.next();
        System.out.println(getResult(arr,num));
    }

    private static String getResult(Integer[] arr, String num) {
        ArrayList<Integer> link1 = new ArrayList<>();
        ArrayList<Integer> link2 = new ArrayList<>();
        // 增序
        Arrays.sort(arr,(a,b)->a-b);
        for (Integer i : arr) {
            if(i<4){
                link1.add(i);
            }else{
                link2.add(i);
            }
        }
        int len1 = link1.size();
        int len2 = link2.size();
        // 获取可能组合
        List<List<Integer>> ans = new ArrayList<>();
        switch (num){
            case "1":
                if(len1==1||len2==1){
                    if(len1 == 1)
                        dfs(link1,0,1,new ArrayList<>(),ans);
                    if(len2 == 1)
                        dfs(link2,0,1,new ArrayList<>(),ans);
                }else if(len1==3||len2==3){ // 只需要命中一条规则
                    if(len1 == 3)
                        dfs(link1,0,1,new ArrayList<>(),ans);
                    if(len2 == 3)
                        dfs(link2,0,1,new ArrayList<>(),ans);
                }else if(len1==2||len2==2){
                    if(len1 == 2)
                        dfs(link1,0,1,new ArrayList<>(),ans);
                    if(len2 == 2)
                        dfs(link2,0,1,new ArrayList<>(),ans);
                }else if(len1==4||len2==4){
                    if(len1 == 4)
                        dfs(link1,0,1,new ArrayList<>(),ans);
                    if(len2 == 4)
                        dfs(link2,0,1,new ArrayList<>(),ans);
                }
                break;
            case "2":
                if(len1==2||len2==2){
                    if(len1 == 2)
                        dfs(link1,0,2,new ArrayList<>(),ans);
                    if(len2 == 2)
                        dfs(link2,0,2,new ArrayList<>(),ans);
                }else if(len1==4||len2==4){
                    if(len1 == 4)
                        dfs(link1,0,2,new ArrayList<>(),ans);
                    if(len2 == 4)
                        dfs(link2,0,2,new ArrayList<>(),ans);
                } else if(len1==3||len2==3){
                    if(len1 == 3)
                        dfs(link1,0,2,new ArrayList<>(),ans);
                    if(len2 == 3)
                        dfs(link2,0,2,new ArrayList<>(),ans);
                }
                break;
            case "4":
                if(len1==4||len2==4){
                    if(len1 == 4)
                        ans.add(link1);
                    if(len2 == 4)
                        ans.add(link2);
                }
                break;
            case "8":
                if(len1==4 && len2==4){
                    ans.add(Stream.concat(link1.stream(),link2.stream()).collect(Collectors.toCollection(ArrayList<Integer>::new)));
                }
                break;
        }
        return ans.toString();
    }
    private static void dfs(ArrayList<Integer> arr, int index, int level, ArrayList<Integer> path, List<List<Integer>> ans) {
        if(path.size() == level){
            // 拷贝当前数组
            ans.add(new ArrayList<>(path));
            return;
        }
        // 回溯
        for(int i=index;i<arr.size();i++){
            path.add(arr.get(i));
            dfs(arr,i+1,level,path,ans);
            path.remove(path.size()-1);
        }
    }
}
